package leetcode_day._2021._202105._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/9 11:46
 * 制作 m 束花所需的最少天数
 * 算法：二分查找
 * 跟 1011 有点像
 * 先求出最少天数的范围  min(bloomDay) <= min <= max(bloomDay)
 * 使用二分查找，找到中间值
 * 然后看这个值是否能够满足要求，制作 m 束花
 * 如果不能满足，就往右移
 * 能够满足，则往左移，看看有没有更小的
 */
public class _09_1482 {

    public int minDays(int[] bloomDay, int m, int k) {
        if (bloomDay.length < m * k) return -1;
        int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
        for (int i = 0; i < bloomDay.length; i++) {
            left = left > bloomDay[i] ? bloomDay[i] : left;
            right = right > bloomDay[i] ? right : bloomDay[i];
        }
        while (left < right) {
            int mid = (left + right) >> 1, cur = 0, flower = 0;
            for (int day : bloomDay) {
                if (day <= mid) {
                    ++flower;
                    if (flower == k) {
                        ++cur;
                        flower = 0;
                    }
                } else flower = 0;
            }
            if (cur >= m) right = mid;
            else left = mid + 1;
        }
        return left;
    }
}
